package com.future;

import java.util.Arrays;

/**
 * Description:
 * 给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
 * <p>
 * 返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
 * <p>
 * 注意：本题相对书上原题稍作改动
 * <p>
 * 示例：
 * <p>
 * 输入：
 * [
 * [-1,0],
 * [0,-1]
 * ]
 * 输出：[0,1,0,1]
 * 解释：输入中标粗的元素即为输出所表示的矩阵
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/max-submatrix-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author: future
 * @Date:2022/3/23:22:03
 */
public class Solution_1724 {

    public static void main(String[] arg) {
        int[][] m = {
                {-1, 0},
                {0, -1}
        };
        m = new int[][]{
                {10, 2, -9, 10, -2},
                {3, -1, -1, 10, -9},
        };
        m = new int[][]{
                {9, -8, 1, 3, -2},
                {-3, 7, 6, -2, 4},
                {6, -4, -4, 8, -7}
        };
        //m = new int[][]{{-100, 300, -50, 200}};
        int[] ans = getMaxMatrix(m);
        System.out.println(Arrays.toString(ans));
    }

    /**
     * m = new int[][]{
     * {9, -8, 1, 3, -2},
     * {-3, 7, 6, -2, 4},
     * {6, -4, -4, 8, -7}
     * };
     * 过程：
     * 从第0行开始
     * {9, -8, 1, 3, -2}，
     * sumArr={9, -8, 1, 3, -2}
     * 一次遍历，求和，如果大于当前最大和，更新坐标
     * 从第0~1行
     * {
     * {9, -8, 1, 3, -2},
     * {-3, 7, 6, -2, 4}
     * }，
     * 数组压缩
     * sumArr={6, -1, 7, 1, 2}
     * 从第0~2行
     * {
     * {9, -8, 1, 3, -2},
     * {-3, 7, 6, -2, 4}
     * {6, -4, -4, 8, -7}
     * }，
     * 数组压缩
     * sumArr={12, -5, 3, 9, -5}
     * <p>
     * 从第1行开始
     * {-3, 7, 6, -2, 4}，
     * sumArr={-3, 7, 6, -2, 4}
     * 一次遍历，求和，如果大于当前最大和，更新坐标
     * * 从第1~2行
     * {
     * {-3, 7, 6, -2, 4},
     * {6, -4, -4, 8, -7}
     * }，
     * 数组压缩
     * sumArr={3, 3, 2, 6, -3}
     * <p>
     * 从第2行开始
     * {6, -4, -4, 8, -7}，
     * sumArr={6, -4, -4, 8, -7}
     * 一次遍历，求和，如果大于当前最大和，更新坐标
     * =========注意：当当前累加和小于0时，要特殊处理
     *
     * @param matrix
     * @return
     */
    public static int[] getMaxMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return new int[0];
        }
        int r1 = 0;
        int c1 = 0;
        int r2 = 0;
        int c2 = 0;
        int N = matrix.length;
        int M = matrix[0].length;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            int[] sumArr = new int[M];
            for (int j = i; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    sumArr[k] += matrix[j][k];
                }
                int curVal = 0;
                // 左上角列默认从0开始
                int begin = 0;
                for (int l = 0; l < M; l++) {
                    curVal += sumArr[l];
                    if (curVal > max) {
                        // 左上角横坐标
                        r1 = i;
                        c1 = begin;
                        // 右下角横坐标
                        r2 = j;
                        // 右下角列坐标
                        c2 = l;
                        max = curVal;
                    } else if (curVal < 0) {
                        // 注意：当当前累加和小于0时，要特殊处理
                        curVal = 0;
                        // 重新设置设置列的开始位置
                        begin = l + 1;
                    }
                }
            }
        }
        return new int[]{r1, c1, r2, c2};
    }

    private static int getMaxSum(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int curVal = 0;
        for (int i = 0; i < nums.length; i++) {
            curVal += nums[i];
            ans = Math.max(curVal, ans);
            curVal = curVal < 0 ? 0 : curVal;
        }
        return ans;
    }

}
